package leetcode.code0373;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 执行用时：7 ms, 在所有 Java 提交中击败了89.85%的用户
 *
 * 内存消耗：48.3 MB, 在所有 Java 提交中击败了91.13%的用户
 *
 * 通过测试用例：32 / 32
 */
public class Solution4 implements IDebug {
	public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
		List<List<Integer>> ans = new ArrayList<>();
		int len1 = nums1.length, len2 = nums2.length;
		boolean[][] seen = new boolean[Math.min(len1, k) + 1][Math.min(len2, k) + 1];// boolean[len1][len2] 这个超内存啊，坑
		PriorityQueue<int[]> p = new PriorityQueue<>((a, b) -> nums1[a[0]] + nums2[a[1]] - (nums1[b[0]] + nums2[b[1]]));
		seen[0][0] = true;
		p.add(new int[] { 0, 0 });
		int n1, n2;
		while (k > 0 && !p.isEmpty()) {
			int[] cur = p.poll();
			List<Integer> list = new ArrayList<>();
			list.add(nums1[n1 = cur[0]]);
			list.add(nums2[n2 = cur[1]]);
			ans.add(list);
			k--;
			int next = n1 + 1;
			if (next < len1 && !seen[next][n2]) {
				p.add(new int[] { next, n2 });
				seen[next][n2] = true;
			}
			next = n2 + 1;
			if (next < len2 && !seen[n1][next]) {
				p.add(new int[] { n1, next });
				seen[n1][next] = true;
			}
		}
		return ans;
	}

	@Override
	public void debug1() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[1,2],[1,4],[1,6]]");
		HelpDebug.compare(e, this.kSmallestPairs(HelpDebug.str2array3("[1,7,11]"), HelpDebug.str2array3("[2,4,6]"), 3));
	}

	@Override
	public void debug2() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[1,3],[2,3]]");
		HelpDebug.compare(e, this.kSmallestPairs(HelpDebug.str2array3("[1,2]"), HelpDebug.str2array3("[3]"), 3));
	}

	@Override
	public void debug3() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[1,1],[1,1]]");
		HelpDebug.compare(e, this.kSmallestPairs(HelpDebug.str2array3("[1,1,2]"), HelpDebug.str2array3("[1,2,3]"), 2));
	}

	@Override
	public void debug4() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[1,1],[1,1],[2,1],[1,2],[1,2],[2,2],[1,3],[1,3],[2,3]]");
		HelpDebug.compare(e, this.kSmallestPairs(HelpDebug.str2array3("[1,1,2]"), HelpDebug.str2array3("[1,2,3]"), 10));
	}

	public void debug5() {
		List<List<Integer>> e = HelpDebug
				.str2intlist1("[[-10,3],[-10,5],[-10,6],[-10,7],[-10,8],[-4,3],[-4,5],[-4,6],[0,3],[0,3]]");
		HelpDebug.compare(e, this.kSmallestPairs(HelpDebug.str2array3("[-10,-4,0,0,6]"), HelpDebug.str2array3("[3,5,6,7,8,100]"), 10));
	}

	public void debug6() {
		List<List<Integer>> e = HelpDebug
				.str2intlist1("[[-10,3],[-10,5],[-10,6],[-10,7],[-10,8],[-4,3],[-4,5],[-4,6],[0,3],[0,3]]");
		HelpDebug.compare(e, this.kSmallestPairs(HelpDebug.str2array3("[1,2]"), HelpDebug.str2array3("[3]"), 3));
	}

	public static void main(String[] args) {
		Solution4 so = new Solution4();
//		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();
		so.debug5();
		so.debug6();

	}

}
